#include <iostream>
#include "Spectrum.h"
#include <time.h>
#include <map>
#include <algorithm>
#define KOSMOS 999999

using namespace std;

int bestVal = KOSMOS +1; 
vector<OLIGO> best; 
vector<OLIGO> * instance;
vector<OLIGO> * many;
Spectrum * sp;

map<std::string ,  vector<OLIGO> >  matrix;

int progress = 0 ;


std::string GetKey(std::vector<NUCLEOTIDE> *nucleo)
{
	std::string result = "";
	for(std::vector<NUCLEOTIDE>::iterator i = nucleo->begin(); i < nucleo->end(); ++i)
	{
		string addon;

		switch((*i))
		{
		case NUCLEOTIDE::A:
			addon = "A";
			break;
		case NUCLEOTIDE::C:
			addon = "C";
			break;
		case NUCLEOTIDE::G:
			addon = "G";
			break;
		case NUCLEOTIDE::T:
			addon = "T";
			break;
		}
		result += addon;
	}

	return result;
}



int evalGreedy(OLIGO a, OLIGO b) 
{
	vector<OLIGO> * chain = new vector<OLIGO>();
	chain->push_back(a);
	chain->push_back(b);

	int offset = 0;
	vector<NUCLEOTIDE> nucleotideChain = vector<NUCLEOTIDE>();  

	for(int i=0;i< chain->at(0).GetLength(); i++)
		nucleotideChain.push_back(chain->at(0).val[i]);

	for (int i = 0;i < chain->size()-1; i++)
	{
		int k = 0;		
		int tempOffset = 0;

		bool flag = false;
		for (int j = 0; j < chain->at(i).GetLength(); j++)
		{
			if(k==chain->at(i+1).val.size())
				break;

			if(chain->at(i).val[j] == chain->at(i+1).val[k])
			{
				k++;
				flag =true;
			}
			else
			{

				if(flag)
				{
					j-=k;
					//j++;
					flag = false;
				}
				k=0;
				tempOffset++;
				//offset++;
			}				
		}			
		offset += tempOffset * tempOffset * tempOffset;

		int begIndex = chain->at(i+1).GetLength() + tempOffset - chain->at(i).GetLength();

		if(begIndex < 0)
		{
			return KOSMOS;
		}

		begIndex = chain->at(i+1).GetLength() - begIndex;
		for(; begIndex< chain->at(i+1).GetLength(); begIndex++)
		{
			nucleotideChain.push_back(chain->at(i+1).val[begIndex]);
		}
	}
	return offset;
}
bool cmp(std::pair<OLIGO,int> a, std::pair<OLIGO,int> b)
{
	return a.second < b.second;
}
vector<OLIGO> * shallowGreedy(OLIGO last)
{
	vector<std::pair<OLIGO,int> > * chain = new vector<std::pair<OLIGO,int> >();

	vector<OLIGO> spectrum = *instance;


	for (int j =0; j< spectrum.size(); j++)
	{
		int e = evalGreedy(last, spectrum.at(j));
		chain->push_back(std::make_pair(spectrum.at(j), e));
	}

	sort(chain->begin(), chain->end(),cmp);

	vector<OLIGO> *chainTemp = new vector<OLIGO>;
	chainTemp->resize(chain->size());
	for (int j =0; j< spectrum.size(); j++)
	{
		chainTemp->at(j) = chain->at(j).first;
	}

	delete chain;
	return chainTemp;
}

vector<OLIGO> * Greedy() 
{
	int length = KOSMOS;
	int eval = KOSMOS;
	int bInd = -1;
	vector<OLIGO> * chain = new vector<OLIGO>();
	vector<OLIGO> spectrum = sp->set;

	chain->push_back(spectrum.at(0));
	spectrum.erase(spectrum.begin());
	while(!spectrum.empty())
	{
		length = KOSMOS;
		eval = KOSMOS;
		bInd = -1;
		for (int j =0; j< spectrum.size(); j++)
		{
			int e = evalGreedy(*(chain->rbegin()), spectrum.at(j));
			if ((e < eval) || (e == eval && spectrum.at(j).GetLength()<length))
			{
				eval = e;
				length = spectrum.at(j).GetLength();
				bInd = j;
			}			
		}
		chain->push_back(spectrum.at(bInd));
		spectrum.erase(spectrum.begin() + bInd);
	}

	return chain;
}


int eval(vector<OLIGO> * chain, int length = sp->getLength(), bool print =false) 
{
	
	//if(progress %10000 == 0)
		//cout<<progress<<"  "<<bestVal<<":"<<endl;


	int offset = 0;
	vector<NUCLEOTIDE> nucleotideChain = vector<NUCLEOTIDE>();  

	for(int i=0;i< chain->at(0).GetLength(); i++)
		nucleotideChain.push_back(chain->at(0).val[i]);

	//int last = 0;
	for (int i = 0;i < chain->size()-1; i++)
	{
		//int maxL = chain->at(i).GetLength() > chain->at(i+1).GetLength()? chain->at(i).GetLength(): chain->at(i+1).GetLength();
		int k = 0;		
		int tempOffset = 0;

		bool flag = false;
		for (int j = 0; j < chain->at(i).GetLength(); j++)
		{


			if(k==chain->at(i+1).val.size())
				break;

			if(chain->at(i).equal(chain->at(i+1)) && j == 0)
			{
				//printf("ble\n");
				tempOffset++;
				continue;
			}

			if(chain->at(i).val[j] == chain->at(i+1).val[k])
			{
				k++;
				flag =true;
			}
			else
			{

				if(flag)
				{
					j-=k;
					//j++;
					flag = false;
				}
				k=0;
				tempOffset++;
				//offset++;
			}				
		}			
		offset += tempOffset * tempOffset * tempOffset;

		int begIndex = chain->at(i+1).GetLength() + tempOffset - chain->at(i).GetLength();

		if(begIndex < 0)
		{
			return KOSMOS;
		}

		begIndex = chain->at(i+1).GetLength() - begIndex;
		for(; begIndex< chain->at(i+1).GetLength(); begIndex++)
		{
			nucleotideChain.push_back(chain->at(i+1).val[begIndex]);
		}
	}

	if(print)
		cout<<GetKey(&nucleotideChain)<<endl;

	if(length >= 0 && nucleotideChain.size() != length)
		return KOSMOS;

	if(length == -1)
		if( nucleotideChain.size() > sp->getLength())
			return KOSMOS;

	//int penalty = sp->getLength() - nucleotideChain.size() + chain->rbegin()->GetBindingEnergy() - sp->getMaxEnergy();
	int penalty = (instance->size() - chain->size())/2;
	if (nucleotideChain.size() + penalty > sp->getLength() && length != -2)
	{
		//	printf("TEST");
		return KOSMOS;
	}
	
	if (penalty >0) 
		offset += penalty-1; //-1 bo tak

	return offset;
}



void BB(vector<OLIGO> chain, OLIGO ol, int nextOligo, int depth = 0)
{
	chain.push_back(ol);
	//instance = shallowGreedy(ol);
	vector<OLIGO> * instance = & matrix[GetKey(&ol.val)];

	if (eval(&chain,-1) >= bestVal)
	{
		//	printf("Odciecie lvl %d\n", depth);
		return;
	}
	progress++;
	if (chain.size() == instance->size())
	{
	//	printf("Reached the bottom\n");
		int val = eval(&chain);

		if (bestVal>val)
		{
			bestVal = val;
			best = chain;
		}
		return; 
	}

	for(int i = 0; i < instance->size(); i++)
	{
	//	if(depth==0)
		//	printf("%d %0.2f \n", depth, (float)i/instance->size());
		int index = (i+nextOligo) % instance->size();

		//if(GetKey(&ol.val) == "GGG")
		//{
			//printf("Fu\n");
		//}

		bool contains = false;
		int licznik =0;
		for(int k = 0; k<chain.size()/* && !contains*/; k++)
			if(chain[k].equal(instance->at(index)))
			{
				licznik++;
				contains = true;
			}
		
		if(instance->at(index).getRepetitionTwo()>0.5 && licznik < 2 && contains)
		{
			contains = false;
		//	if(GetKey(&ol.val) == "GGG")
		//	{
				//printf("VFSS\n");
		//	}
		}
		if(instance->at(index).getRepetitionMany()>0.5)
			contains = false;



		if(!contains)
			BB(chain,instance->at(index), (i+1)%instance->size(), depth +1);		
	}	

}


OLIGO parse(string val)
{
	OLIGO o = OLIGO();
	for(int i=0; i< val.size(); i++)
	{
		switch(val[i])
		{
		case 'A': o.val.push_back(A); break;
		case 'C': o.val.push_back(C); break;
		case 'T': o.val.push_back(T); break;
		case 'G': o.val.push_back(G); break;
		}
	}
	return o;
}

void prepareMatrix()
{
	for (int i =0 ;i< instance->size(); i++)
	{		
		matrix[GetKey(&instance->at(i).val)] = *(shallowGreedy(instance->at(i)));
	}
}


int main(int argc, char ** argv)
{
	sp = new Spectrum();
	sp->load(std::string(argv[1]));
	time_t t = time(NULL);
	instance = Greedy();
//	many = new vector<OLIGO>();
//	vector<OLIGO> temp;
	/*for (vector<OLIGO>::iterator i = instance->begin();i!=instance->end();i++)
	{
		if( i->getRepetitionTwo()>0.5)
			temp.push_back(*i);

		if( i->getRepetitionMany()>0.5)
		{
			temp.push_back(*i);
			temp.push_back(*i);			
		}
	}
	for(int i =0; i<temp.size();i++)
	{
		instance->push_back(temp[i]);
	}*/

	prepareMatrix();
	bestVal = eval(instance,-2) +1;

	BB(vector<OLIGO>(),instance->at(0),1);
	//long double val = 1; 
	//for(int i=1; i <= atoi(argv[2]); i++)
		//val *=i;
	printf("%s ", argv[2]);
	printf("%d \n", progress);
	/*for (int i=0;i<best.size();i++)
	{
		cout<<GetKey(&(best[i].val));
		std::cout<<"\n";
	}*/

	/*best = vector<OLIGO>();
	OLIGO o = OLIGO();
	o.val.push_back(T);
	o.val.push_back(C);
	o.val.push_back(G);
	o.val.push_back(G);
	best.push_back(o);

	o = OLIGO();
	o.val.push_back(C);
	o.val.push_back(G);
	o.val.push_back(G);
	best.push_back(o);

	o = OLIGO();
	o.val.push_back(G);
	o.val.push_back(G);
	o.val.push_back(C);
	best.push_back(o);

	o = OLIGO();
	o.val.push_back(G);
	o.val.push_back(C);
	o.val.push_back(G);	
	best.push_back(o);

	o = OLIGO();
	o.val.push_back(G);
	o.val.push_back(C);
	o.val.push_back(G);	
	o.val.push_back(A);		
	best.push_back(o);

	o = OLIGO();
	o.val.push_back(G);
	o.val.push_back(C);
	o.val.push_back(G);
	o.val.push_back(A);
	o.val.push_back(A);
	best.push_back(o);*/

	/*best = vector<OLIGO>();
	best.push_back(parse("TTTAATTG"));
	best.push_back(parse("TTTAATTGT"));
	best.push_back(parse("TTAATTGT"));
	best.push_back(parse("TTAATTGTA"));
	best.push_back(parse("TAATTGTA"));
	best.push_back(parse("TAATTGTAT"));
	best.push_back(parse("AATTGTAT"));
	best.push_back(parse("ATTGTAT"));
	best.push_back(parse("TTGTATC"));
	best.push_back(parse("TGTATC"));
	best.push_back(parse("GTATC"));

	eval(&best,-1,true);*/
	//if(best.size()>0)
		//eval(&best,sp->getLength(),true);
	/*
	else 
		cout<<"Brak rozwiazania"<<endl;
	cout<<bestVal;*/
	//system("PAUSE");
	return 0;
}
